Controlled stochastic processes for simulated annealing

Abstract: Simulated annealing solves optimization problems by means of a random walk in an energy landscape based on the objective function and a temperature parameter. By slowly decreasing the temperature, the algorithm converges to the global optimal solution, also for nonconvex functions. However, if the temperature is decreased too quickly, this procedure often gets stuck in local minima. To overcome this, we here present a new perspective on simulated annealing. More precisely, we consider the cooling landscape as a curve of probability measures and prove that there exists a minimal norm velocity field which solves the continuity equation. The latter is a differential equation which governs the evolution of the aforementioned curve. The solution is the weak gradient of an integrable function, which is in line with the interpretation of the velocity field as a derivative of optimal transport maps. We also show that controlling stochastic annealing processes by superimposing this velocity field would allow them to follow arbitrarily fast cooling schedules. Based on these findings, we design novel interacting particle based optimization methods, convergent optimal transport based approximations to this control, that accelerate simulated annealing processes. This acceleration behavior is also validated on a number of numerical experiments.

machine learningprobabilitystatistics theory

Audience: researchers in the discipline

( paper )

Gothenburg statistics seminar

Series comments: Gothenburg statistics seminar is open to the interested public, everybody is welcome. It usually takes place in MVL14 (http://maps.chalmers.se/#05137ad7-4d34-45e2-9d14-7f970517e2b60, see specific talk). Speakers are asked to prepare material for 35 minutes excluding questions from the audience.